package com.chapter4.graph.sp;

import java.util.Stack;

/**
 * 
* @ClassName: AcyclicSP 
* @Description: 无环有向图的最短路径
* 
*  利用拓扑排序
*  
* @author minjun
* @date 2015年3月15日 上午12:12:27 
*
 */
public class AcyclicSP {
	
	private DirectEdge[] edgeTo;
	
	private double[] distTo; 

	public AcyclicSP(DirectWeightGraph g,int s){
		DirectWeightCycle dwc=new DirectWeightCycle(g);
		if(dwc.hasCycle()) throw new RuntimeException("有环。。。。");
		
		edgeTo=new DirectEdge[g.V()];
		distTo=new double[g.V()];
		for(int i=0;i<g.V();i++){
			distTo[i]=Double.POSITIVE_INFINITY;
		}
		distTo[s]=0.0;
		Topological top=new Topological(g);
		for(int v:top.topOrder()){
			for(DirectEdge edge:g.adj(v)){
				relax(edge);
			}
		}
	}
	
	private void relax(DirectEdge edge){
		int v=edge.from();
		int w=edge.to();
		if(distTo[w]>distTo[v]+edge.weight()){
			distTo[w]=distTo[v]+edge.weight();
			edgeTo[w]=edge;
		}
	}
	
	/**
	 * 
	* @Title: hasPathTo 
	* @Description: 是否可达 
	* @param @param v
	* @param @return    设定文件 
	* @return boolean    返回类型 
	* @throws
	 */
	public boolean hasPathTo(int v){
		return distTo[v]<Double.POSITIVE_INFINITY;
	}
	
	/**
	 * 
	* @Title: pathTo 
	* @Description: 到v的最短路径 
	* @param @param v
	* @param @return    设定文件 
	* @return Iterable<DirectEdge>    返回类型 
	* @throws
	 */
	public Iterable<DirectEdge> pathTo(int v){
		Stack<DirectEdge> stack=new Stack<DirectEdge>();
		for(DirectEdge edge=edgeTo[v];edge!=null;edge=edgeTo[edge.from()]){
			stack.push(edge);
		}
		
		Stack<DirectEdge> edges=new Stack<DirectEdge>();
		while(!stack.isEmpty()){
			edges.push(stack.pop());
		}
		return edges;
	}

	public double distTo(int v) {
		return distTo[v];
	}
	
}
